package m202406.d09;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/6/9 12:56
 */

/**
 * '(' n=q的组合 ')' n=p的组合    p+q=n-1;
 */
public class Q22 {

    Map<Integer, List<String>> cache = new HashMap<>();

    public List<String> generateParenthesis(int n) {
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        List<String> res = new ArrayList<>();
        if (n == 0) {
            return new ArrayList<>(List.of(""));
        }
        if (n == 1) {
            return new ArrayList<>(List.of("()"));
        }
        for (int i = 0; i < n; i++) {
            List<String> list1 = generateParenthesis(i);
            List<String> list2 = generateParenthesis(n - i-1);
            for (String s1 : list1) {
                for (String s2 : list2) {
                    res.add("(" + s1 + ")" + s2);
                }
            }
        }
        cache.put(n, res);
        return res;
    }
}
